package com.platform.modules.alg.alglib.poj3264;

import static java.lang.Integer.max;
import static java.lang.Integer.min;

public class Poj3264Block {
    public final int inf = 0x3f3f3f3f;
    public final int maxn = 50010;
    int L[] = new int[maxn];
    int R[] = new int[maxn];
    int belong[] = new int[maxn];
    int block_max[] = new int[maxn];
    int block_min[] = new int[maxn];
    int a[] = new int[maxn];
    int n;
    int m;

    public String output = "";

    void build() {
        int t = (int) Math.sqrt(n);
        int num = n / t;
        if (n % num != 0) num++;
        for (int i = 1; i <= num; i++) {
            L[i] = (i - 1) * t + 1;
            R[i] = i * t;
        }

        R[num] = n;
        for (int i = 1; i <= n; i++)
            belong[i] = (i - 1) / t + 1;
        // 求每块最值
        for (int i = 1; i <= num; i++) {
            int MIN = inf, MAX = -inf;
            for (int j = L[i]; j <= R[i]; j++) {
                MAX = max(MAX, a[j]);
                MIN = min(MIN, a[j]);
            }
            block_max[i] = MAX;
            block_min[i] = MIN;
        }
    }

    int query(int l, int r) {
        int MIN = inf, MAX = -inf;
        if (belong[l] == belong[r]) {
            for (int i = l; i <= r; i++) {
                MAX = max(MAX, a[i]);
                MIN = min(MIN, a[i]);
            }
            return MAX - MIN;
        } else {
            for (int i = l; i <= R[belong[l]]; i++) {//左端
                MAX = max(MAX, a[i]);
                MIN = min(MIN, a[i]);
            }
            for (int i = belong[l] + 1; i < belong[r]; i++) {//中间
                MAX = max(MAX, block_max[i]);
                MIN = min(MIN, block_min[i]);
            }
            for (int i = L[belong[r]]; i <= r; i++) {//右端
                MAX = max(MAX, a[i]);
                MIN = min(MIN, a[i]);
            }
        }
        return MAX - MIN;
    }

    public String cal(String input) {
        int l, r;
        String[] line = input.split("\n");
        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);

        // 下标从1开始
        for (int i = 1; i <= n; i++)
            a[i] = Integer.parseInt(line[i]);
        build();
        for (int j = 1; j <= m; j++) {
            String[] command = line[n + j].split(" ");
            l = Integer.parseInt(command[0]);
            r = Integer.parseInt(command[1]);
            output += query(l, r) + "\n";
        }

        return output;
    }
}
